/*
 * CopyRight(C) Kenbin
 */

#ifndef LSG_HASHFILE_INCLUDED
#define LSG_HASHFILE_INCLUDED

#if __GNUC__ == 4
#include <tr1/functional>
#else
#include <hash_map>
#endif

#include "lsg_config.h"

namespace LSG {

#define MAX_FILE_LEN 100000000

#define NODE_FREE -1
#define NODE_NULL 0
#define NODE_DELETE 0

/*
   ------------------------------------ <----headblock
   |              | bucket_head_count |
   |              ---------------------
   |              | common_node_count |
   |              ---------------------
   |              | common_node_used  |
   |              ---------------------
   |              | total_used        |
   |              ---------------------
   |              | file_len          |
   |              --------------------- <----nodes
   |              |                   |
   |              |                   |
   |              |                   | 1
   |              ---------------------
 file_len              ...........
   |              ---------------------
   |              |                   |
   |              |                   |
   |              |                   | n
   ------------------------------------

   n = bucket_head_count + common_node_count
   total_used = bucket_head_used + common_node_used
*/

    struct HeadBlock
    {
	unsigned bucket_head_count;
	unsigned common_node_count;
	unsigned common_node_used;
	unsigned total_used;
	unsigned file_len;
    };

    template <typename K, typename V>
	struct Node
	{
	    int next;
	    K key;
	    V value;
	};

    template <typename K, typename V>
	class THashFile
	{
	    public:
		THashFile(char *filename, unsigned bucket_head_count, 
			unsigned common_node_count);
		virtual ~THashFile();

		int Add(const K &key, const V &value);
		int Set(const K &key, const V &value);
		int Get(const K &key, V *value);
		int Delete(const K &key); /* only mark */

	    public:
		bool Error() const
		{
		    if(m_errid != 0) {
			return true;
		    }

		    return false;
		}

		const char *ErrMsg()
		{
		    switch(m_errid) {
			case 1: return "truncate file fail";
			case 2: return "open_and_mmap file fail";
			default: return "undefined";
		    }
		}

	    private:
		THashFile(const THashFile &right);

		int truncate_file(const char *filename, 
			unsigned bucket_head_count = 1024, 
			unsigned common_node_count = 1024);
		int extend_file(unsigned extend_count = 1024);
		int find(const K &key, unsigned hash, Node<K, V> **node);
		int open_and_mmap_file(const char *filename);
		void munmap_file();
		unsigned make_hash(const K &key);	

		char m_filename[256];
		HeadBlock *m_headblock;
		Node<K, V> *m_nodes;

		unsigned m_max_nodecount; /* for verify 'next' */
		unsigned m_access_count;

		int m_errid;
	};

    template <typename K, typename V>
	THashFile<K, V>::THashFile(char *filename, unsigned bucket_head_count,
		unsigned common_node_count)
	{
	    m_headblock = NULL;
	    m_nodes = NULL;

	    m_max_nodecount = 0;
	    m_access_count = 0;

	    m_errid = 0;

	    int e = 0;
	    if((e = open_and_mmap_file(filename)) != 0)
	    {
		if(e == -1)
		{
		    if((e = truncate_file(filename, bucket_head_count, 
				    common_node_count)) != 0) 
		    {
			m_errid = 1;
			return;
		    }

		    if((e = open_and_mmap_file(filename)) != 0) 
		    {
			m_errid = 2;
			return;
		    }
		} 
		else 
		{
		    m_errid = 2;
		    return;
		}
	    }
	}

    template <typename K, typename V>
	THashFile<K, V>::~THashFile()
	{
	    munmap_file();
	}

    template <typename K, typename V>
	int THashFile<K, V>::Add(const K &key, const V &value)
	{
	    unsigned hash = make_hash(key);
	    hash %= m_headblock->bucket_head_count;

	    if(hash > m_max_nodecount) {
		return LSG_HASHFILE_MAYBE_DAMAGED;
	    }

	    Node<K, V> *bucket = m_nodes + hash;
	    Node<K, V> *node = NULL;

	    int e = find(key, hash, &node);
	    /* exist, fail */
	    if(e == 0) {
		return -1;
	    }

	    if(bucket->next == NODE_FREE)
	    {
		bucket->next = NODE_NULL;
		node = bucket;
		m_headblock->total_used ++;
	    }

	    if(node == NULL)
	    {
		if(m_headblock->common_node_used >= m_headblock->common_node_count) {
		    if(extend_file(m_headblock->total_used) != 0) {
			return LSG_HASHNODE_EXHAUSTED;
		    }

		    bucket = m_nodes + hash;
		}

		unsigned total_alloced = m_headblock->bucket_head_count 
		    + m_headblock->common_node_used;

		if(total_alloced > m_max_nodecount) {
		    return LSG_HASHFILE_MAYBE_DAMAGED;
		}

		node = m_nodes + total_alloced;

		node->next = bucket->next;
		bucket->next = total_alloced;

		m_headblock->common_node_used ++;
		m_headblock->total_used ++;
	    }

	    memcpy(&(node->key), &key, sizeof(K));
	    memcpy(&(node->value), &value, sizeof(V));

	    m_access_count ++;
	    return 0;
	}

    template <typename K, typename V>
	int THashFile<K, V>::Set(const K &key, const V &value)
	{
	    unsigned hash = make_hash(key);
	    hash %= m_headblock->bucket_head_count;

	    if(hash > m_max_nodecount) {
		return LSG_HASHFILE_MAYBE_DAMAGED;
	    }

	    Node<K, V> *bucket = m_nodes + hash;
	    Node<K, V> *node = NULL;

	    int e = find(key, hash, &node);
	    /* exist, update */
	    if(e == 0) {
		memcpy(&(node->value), &value, sizeof(V));

		m_access_count ++;
		return 0;
	    }

	    if(bucket->next == NODE_FREE)
	    {
		bucket->next = NODE_NULL;
		node = bucket;
		m_headblock->total_used ++;
	    }

	    if(node == NULL)
	    {
		if(m_headblock->common_node_used >= m_headblock->common_node_count) {
		    if(extend_file(m_headblock->total_used) != 0) {
			return LSG_HASHNODE_EXHAUSTED;
		    }

		    bucket = m_nodes + hash;
		}

		unsigned total_alloced = m_headblock->bucket_head_count 
		    + m_headblock->common_node_used;

		if(total_alloced > m_max_nodecount) {
		    return LSG_HASHFILE_MAYBE_DAMAGED;
		}

		node = m_nodes + total_alloced;

		node->next = bucket->next;
		bucket->next = total_alloced;

		m_headblock->common_node_used ++;
		m_headblock->total_used ++;
	    }

	    memcpy(&(node->key), &key, sizeof(K));
	    memcpy(&(node->value), &value, sizeof(V));

	    m_access_count ++;
	    return 0;
	}

    template <typename K, typename V>
	int THashFile<K, V>::Get(const K &key, V *value)
	{
	    unsigned hash = make_hash(key);
	    hash %= m_headblock->bucket_head_count;

	    if(hash > m_max_nodecount) {
		return LSG_HASHFILE_MAYBE_DAMAGED;
	    }

	    Node<K, V> *node = NULL;
	    int e = find(key, hash, &node);
	    if(e < 0) {
		return e;
	    }

	    *value = node->value;

	    m_access_count ++;
	    return 0;
	}

    template <typename K, typename V>
	int THashFile<K, V>::Delete(const K &key)
	{
	    unsigned int hash = make_hash(key);
	    hash %= m_headblock->bucket_head_count;

	    if(hash > m_max_nodecount) {
		return LSG_HASHFILE_MAYBE_DAMAGED;
	    }

	    Node<K, V> *node = NULL;
	    int e = find(key, hash, &node);
	    if(e < 0) {
		return e;
	    }

	    node->key = NODE_DELETE;

	    m_access_count ++;
	    return 0;
	}

    template <typename K, typename V>
	int THashFile<K, V>::truncate_file(const char *filename, 
		unsigned bucket_head_count, unsigned common_node_count)
	{
	    int fd = open(m_filename, O_RDWR | O_NONBLOCK | O_CREAT, FILE_ACESS_AUTH);
	    if(fd < 0) {
		return -1;
	    }

	    HeadBlock hb;

	    hb.bucket_head_count = bucket_head_count;
	    hb.common_node_count = common_node_count;
	    hb.common_node_used = 0;
	    hb.total_used = 0;
	    unsigned total_node_count = bucket_head_count + common_node_count;
	    hb.file_len = sizeof(HeadBlock) + total_node_count * sizeof(Node<K, V>);

	    if(write(fd, &hb, sizeof(hb)) < sizeof(hb)) {
		return LSG_WRITE_ERR;
	    }

	    Node<K, V> node;
	    memset(&node, 0, sizeof(node));
	    node.next = NODE_FREE;

	    for(int i = 0; i < total_node_count; i ++)
	    {
		if(write(fd, &node, sizeof(node)) < sizeof(node)) {
		    return LSG_WRITE_ERR;
		}
	    }

	    close(fd);
	    return 0;
	}

    template <typename K, typename V>
	int THashFile<K, V>::extend_file(unsigned extend_count)
	{	
	    unsigned source_len = m_headblock->file_len;
	    unsigned extend_len = extend_count * sizeof(Node<K, V>);

	    if(source_len + extend_len >= MAX_FILE_LEN) {
		return LSG_HASHFILE_TOO_LONG;
	    }

	    int fd = open(m_filename, O_RDWR);
	    if(fd < 0) {
		return LSG_OPEN_ERR;
	    }

	    if(lseek(fd, source_len, SEEK_SET) == -1) {
		return LSG_LSEEK_ERR;
	    }

	    if(lseek(fd, extend_len - sizeof(Node<K, V>), SEEK_CUR) == -1) {
		return LSG_LSEEK_ERR;
	    }

	    write(fd, m_nodes, sizeof(Node<K, V>));
	    close(fd);

	    munmap_file();
	    int e = open_and_mmap_file(m_filename);
	    if(e < 0) {
		return e;
	    }

	    unsigned total_node_count = m_headblock->bucket_head_count 
		+ m_headblock->common_node_count;
	    memset(m_nodes + total_node_count, 0, extend_len);

	    m_headblock->common_node_count += extend_count;

	    return 0;
	}

    template <typename K, typename V>
	int THashFile<K, V>::find(const K &key, unsigned hash, Node<K, V> **node)
	{
	    *node = m_nodes + hash;

	    unsigned total_alloced = m_headblock->bucket_head_count 
		+ m_headblock->common_node_used;

	    while(1) 
	    {
		if((*node)->key == key && (*node)->next != NODE_FREE) {
		    return 0;
		}

		if((*node)->key == NODE_DELETE || (*node)->next <= 0
			|| (*node)->next > total_alloced) 
		{
		    *node = NULL;
		    break;
		}

		*node = m_nodes + (*node)->next;
	    }

	    return LSG_HASHNODE_NOT_FOUND;
	}

    template <typename K, typename V>
	int THashFile<K, V>::open_and_mmap_file(const char *filename)
	{
	    snprintf(m_filename, sizeof(m_filename)-1, filename);

	    int fd = open(filename, O_RDWR);
	    if(fd < 0) {
		return LSG_OPEN_ERR;
	    }

	    struct stat st;
	    if(fstat(fd, &st) < 0) {
		return LSG_STAT_ERR;
	    }

	    void *buf = mmap(NULL, st.st_size, 
		    PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
	    close(fd);

	    if(buf == NULL || buf == (void *)MAP_FAILED) {
		return LSG_MMAP_ERR;
	    }

	    m_headblock = (HeadBlock*)buf;
	    m_nodes = (Node<K, V> *)((char*)buf + sizeof(HeadBlock));

	    m_headblock->file_len = st.st_size;
	    m_max_nodecount = (st.st_size - sizeof(HeadBlock)) / sizeof(Node<K, V>);

	    return 0;
	}

    template <typename K, typename V>
	void THashFile<K, V>::munmap_file()
	{
	    if(m_headblock == NULL) {
		return;
	    }

	    munmap(m_headblock, m_headblock->file_len);
	    m_headblock = NULL;
	    m_nodes = NULL;
	    m_access_count = 0;
	}

    template <typename K, typename V>
	unsigned THashFile<K, V>::make_hash(const K &key)
	{
#if __GNUC__ == 4
	    std::tr1::hash<K> H;
#else
	    std::hash<K> H;
#endif

	    return H(key);
	}

}

#endif
